1. Field of the Invention
This invention relates to flash EEPROM memory arrays, and more particularly, to methods and apparatus for finding data stored in advanced flash EEPROM memory arrays.
2. History of the Prior Art
Recently, flash electrically-erasable programmable read only memory (flash EEPROM memory) has been used as a new form of long term storage. A flash EEPROM memory array is constructed of a large plurality of floating-gate metal-oxide-silicon field effect transistor devices arranged as memory cells in typical row and column fashion with circuitry for accessing individual cells and placing the memory transistors of those cells in different memory conditions. The memory transistors may be programmed by storing a charge on the floating gate. This charge remains when power is removed from the array. The charge level may be detected by interrogating the devices. Flash EEPROM memory arrays may be designed to provide a smaller lighter functional equivalent of a hard disk drive which operates more rapidly and is not as sensitive to physical damage. Flash EEPROM memory arrays are especially useful in portable computers where space is at a premium and weight is extremely important.
As originally devised, each flash EEPROM memory cell stores a single bit of data. If a flash EEPROM memory cell is programmed so that charge is stored on the floating gate, the state is typically referred to as a "zero" or programmed state; while if little or no charge is stored on the gate, this is typically considered a "one" or erased state. Recently, it has been discovered that the transistor devices used for flash EEPROM memory arrays may be made to store charge at a number of discrete levels greater than the charge level of the erased state. Essentially, a plurality of discrete levels of charge above the erased level may be stored on the floating gates of the devices during programming and erasing by varying the voltages applied to the terminals of the devices and the duration of application; and these different charge levels (device conditions or states) may be detected. This allows flash EEPROM memory arrays to store more than one bit per flash cell and radically increases the storage capacity of such arrays.
In general, a flash EEPROM memory array is divided into blocks which are connected so that each entire block of memory cells must be erased simultaneously. With N-type complimentary metal-oxide-silicon (CMOS) flash memory cells, this erasure is typically accomplished by a high voltage value applied simultaneously to the source terminals of all the memory transistors of the block while the gate terminals are grounded and the drain terminals are floated. Whether one or more bits are stored in a cell, since all of the source terminals of the memory transistors of a block of the array are joined together, a device having its floating gate in a charged state cannot be switched to the erased state without erasing all of the cells in the entire block of the array. Thus, while an electro-mechanical hard disk drive typically stores information in a first area of the disk and then rewrites that same area of the disk when the information changes, this is not possible with a flash memory array without erasing all of the valid information that remains in that portion of the array along with the invalid (dirty) information. Consequently, in a recently devised arrangement, when the information at a data entry changes, the changed information is written to a new location on a block of the array containing empty (erased) cells rather than written over the old data; and the old data is marked invalid.
Because of this arrangement by which data is replaced by writing it to a different physical position, the physical address at which data is stored varies constantly. Consequently, a logical address is assigned to and accompanies the data to indicate where specific data is stored.
There are a number of problems which arise from the storage of data in a flash EEPROM cell because of this logical addressing scheme. In order to find a physical location at which data is stored, it is necessary to conduct a search for the physical address. Heretofore, an address search has been conducted in a data base which is set up in memory on the flash EEPROM memory array board whenever power is applied to the array. This data base provides a lookup table in which logical and physical addresses are correlated. The search utilizes the flash system controller on the array board. The system controller conducts a lookup to find the logical address in this database whenever the array is accessed. With smaller flash memory arrays, this sort of search for data is feasible because the number of entries is relatively small. However, as the size of arrays has increased, the data base required for such an address search has increased as both the number of entries in the array and the length of each entry has increased until it occupies a very significant amount of the space available on the circuit board. Moreover, since a search of the array is conducted on a serial basis on power up in order to establish the data base initially, the time required for that search has increased as the size of the array has increased. With larger arrays, it has become impossible to finish the search before other requirements of the system cause the search to be discontinued. It has become apparent that the array suffers so greatly from the use of such an arrangement that products so devised are not feasible for large flash EEPROM memory arrays.
It is therefore desirable to provide an improved method and apparatus for conducting a data search in a flash EEPROM memory array.